class Solution
{
public:
    long long minimumCost(string source, string target, vector<char> &original, vector<char> &changed, vector<int> &cost)
    {
        vector<vector<int>> graph(26, vector<int>(26, INT_MAX));
        for (int i = 0; i < original.size(); i++)
        {
            graph[original[i] - 'a'][changed[i] - 'a'] = min(graph[original[i] - 'a'][changed[i] - 'a'], cost[i]);
        }

        auto dijkstra = [&](int start, int end)
        {
            if (start == end)
            {
                return 0;
            }
            vector<int> dist(26, INT_MAX);
            vector<bool> visited(26, false);
            dist[start] = 0;
            for (int i = 0; i < 26; i++)
            {
                int minDist = INT_MAX;
                int minIndex = -1;
                for (int j = 0; j < 26; j++)
                {
                    if (!visited[j] && dist[j] < minDist)
                    {
                        minDist = dist[j];
                        minIndex = j;
                    }
                }
                if (minIndex == -1)
                {
                    break;
                }
                visited[minIndex] = true;
                for (int j = 0; j < 26; j++)
                {
                    if (graph[minIndex][j] != INT_MAX)
                    {
                        dist[j] = min(dist[j], dist[minIndex] + graph[minIndex][j]);
                    }
                }
            }
            return dist[end];
        };

        vector<vector<int>> dists(26, vector<int>(26, INT_MAX));
        for (int i = 0; i < 26; i++)
        {
            for (int j = 0; j < 26; j++)
            {
                dists[i][j] = dijkstra(i, j);
            }
        }

        long long ans = 0;
        for (int i = 0; i < source.size(); i++)
        {
            int dist = dists[source[i] - 'a'][target[i] - 'a'];
            if (dist == INT_MAX)
            {
                return -1;
            }
            ans += dist;
        }
        return ans;
    }
};